# !/usr/bin/env python3
# -*- coding:utf-8 -*-

"""
Insertion Sort - 插入排序
    核心：通过构建有序序列，对于未排序序列，在已排序序列中
        从后向前扫描（对于当前链表则只能从前往后遍历）找到相应位置并插入
        实现上通常使用inplace排序（需要O(1)的额外空间）
            1.从第一个元素开始，该元素可认为已排序
            2.取下一个元素，对已排序数组从后往前扫描
            3.若从排序数组中取出的元素大于新元素，则移至下一位置
            4.重复步骤3，直至找到已排序元素小于等于新元素的位置
            5.插入新元素至该位置
            6.重复2~5
    性质：
        交换操作和数组中倒置的数量相同
        比较次数>=倒置次数，<=倒置的数量加上数组的大小减一
        每次交换都改变了两个顺序颠倒的元素位置，即减少了一对倒置，倒置数量为0时即完成排序
        每次交换对应着一次比较，且1到N-1之间的每个i都可能需要一次额外的记录(a[i]未达到数组左端时)
        最坏情况下需要~N²/2次比较和~N²/2次交换，最好情况下需要N-1次比较和0次交换
        平均情况下需要~N²/4次比较和~N²/4次交换
    复杂度分析：
        时间复杂度平均情况和最坏情况均为O(n²)
        时间复杂度最好情况为O(n)
        空间复杂度为O(1)
    稳定性：稳定
"""

def InsertionSort(alist):
    for i, item_i in enumerate(alist):
        print(alist)
        index = i
        while index > 0 and alist[index - 1] > item_i:
            alist[index] = alist[index - 1]
            index -= 1
        
        alist[index] = item_i
    
    return alist

unsorted_list = [5, 7, 2, 4, 9, 1, 5, 3]
print(InsertionSort(unsorted_list))